// class Solution {
//     public int maxSubArray(int[] nums) {
//         int n = nums.length;
//         int[] dp = new int[n];//定义i下标为最大子数组和
//         dp[0] = nums[0];

//         for(int i = 1; i < n; i++) {
//             dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
//         }
//         int ret = Integer.MIN_VALUE;
//         for(int i = 0; i < n; i++) {
//             if(ret < dp[i]) ret = dp[i];
//         }

//         return ret;
//     }
// }

//上面动规，下面优化成维护一个变量
/**
 * 53. 最大子数组和
 * https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked
 */
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        int cur = nums[0], result = nums[0];

        for(int i = 1; i < n; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            if(result < cur) result = cur;
        }

        return result;
    }
}